package com.cty._01_Base._14_CuttingRope;

/**
 * @Auther: cty
 * @Date: 2020/7/4 9:02
 * @Description: 面试题14：剪绳子
 * 题目：给你一根长度为n绳子，请把绳子剪成m段（m、n都是整数，n>1并且m≥1）。
 * 每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]*k[1]*…*k[m]可能的最大乘
 * 积是多少？例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此
 * 时得到最大的乘积18。
 * @version: 1.0
 */
public class CuttingRope {

    /**
     * 动态规划实现
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(N)
     * @param length
     * @return
     */
    public static int maxProductAfterCutting01(int length){
        if(length < 2)
            return 0;
        if(length == 2)
            return 1;
        if(length == 3)
            return 2;

        int[] products = new int[length + 1];
        products[0] = 0;
        products[1] = 1;
        products[2] = 2;
        products[3] = 3;
        int max;

        for(int i=4; i<=length; i++){
            max = 0;
            for(int j=1; j<=i/2; j++){
                int product = products[j] * products[i-j];
                if(product > max)
                    max = product;
            }
            products[i] = max;
        }

        return products[length];
    }  // end maxProductAfterCutting01()

    /**
     * 贪婪算法实现
     * 时间复杂度：O(1)
     * 空间复杂度：O(1)
     * @param length
     * @return
     */
    public static int maxProductAfterCutting02(int length){
        if(length < 2)
            return 0;
        if(length == 2)
            return 1;
        if(length == 3)
            return 2;

        int timesOf3 = length/3;
        if((length-timesOf3*3) == 1)
            timesOf3 -= 1;

        int timesOf2 = (length-timesOf3*3) / 2;

        return (int)(Math.pow(3,timesOf3) * Math.pow(2,timesOf2));
    }  // end maxProductAfterCutting02()

}  // end class
